import java.util.HashMap;
import java.util.Map;

/**
 * @author ：hzs
 * @date ：Created in 2020/12/29 21:41
 * @description：
 * @modified By：
 * @version: $
 */
public class LRUCache {

    private int capacity;
    private int number;
    private Map<Integer, Node> map;
    // 头最新，尾最旧
    private Node<Integer, Integer> head;
    private Node<Integer, Integer> tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.number = 0;
        this.map = new HashMap<>();
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 删
            remove(node);
            // 插
            addHead(node);
            return (int)node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node<Integer, Integer> node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            // 删
            remove(node);
        } else {
            node = new Node<>();
            map.put(key, node);
            this.number++;
            // 删
            if (number > capacity) {
                map.remove(tail.pre.key);
                remove(tail.pre);
                number--;
            }
        }
        // 改
        node.key = key;
        node.value = value;
        // 插
        addHead(node);
    }

    class Node<K, V> {
        K key;
        V value;
        Node<K, V> pre;
        Node<K, V> next;
    }

    private void addHead(Node node) {
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    private void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(2, 1); // 缓存是 {1=1}
        lRUCache.put(3, 2); // 缓存是 {1=1, 2=2}
        lRUCache.get(2);    // 返回 1
        lRUCache.put(4, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache.get(2);    // 返回 -1 (未找到)
        lRUCache.get(3);    // 返回 3
        lRUCache.get(4);    // 返回 4
    }

}